package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC621 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int leastInterval(char[] tasks, int n) {
            if (n == 0) return tasks.length;

            int[] job = new int[26];
            PriorityQueue<Integer> pTask = new PriorityQueue<>(Collections.reverseOrder());
            for (char task : tasks) ++job[task - 'A'];
            for (int i : job) if (i > 0) pTask.add(i);

            int totalTime = 0;
            while (!pTask.isEmpty()) {
                if (pTask.size() >= n + 1) {
                    totalTime += n + 1;
                } else {
                    if (pTask.peek() == 1) {
                        totalTime += pTask.size();
                        break;
                    } else totalTime += n + 1;
                }

                PriorityQueue<Integer> tempTask = new PriorityQueue<>(Collections.reverseOrder());
                int minusCount = n + 1;
                while (!pTask.isEmpty() && minusCount-- > 0) {
                    int curPeek = pTask.poll();
                    if (curPeek > 1) tempTask.offer(curPeek - 1);
                }

                for (Integer pa : pTask) tempTask.offer(pa);
                pTask = tempTask;
            }

            return totalTime;
        }
    }

    public void run() {
        Solution solution = new Solution();
        char[] tasks = InputUtil.toCharArray("[\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"]");
        System.out.println(solution.leastInterval(tasks, 2));
    }

    public static void main(String[] args) throws Exception {
        LC621 an = new LC621();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
